package 重建二叉树;
//题目描述
//输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
// 假设输入的前序遍历和中序遍历的结果中都不含重复的数字
// 。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
public class Solution
{
    public TreeNode reConstructBinaryTree(int [] pre, int [] in)
    {
        //重点是对于递归时的输入的索引的把握
        //给出先序遍历和中序遍历，先序遍历的首节点就是根节点，中序遍历的首节点在中间，首节点以左就是左子树，右边就是右子树
        //用递归的方法
        return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
    }
    public TreeNode reConstructBinaryTree(int [] pre,int start1,int end1, int [] in,int start2,int end2)
    {
        //判断输入
        if (start1>end1||start2>end2)return null;
        //建立首节点
        int rootData=pre[start1];
        TreeNode head=new TreeNode(rootData);
        //找到根节点所在位置
        int rootindex=findIndexInArray(in,rootData,start2,end2);
        int l=rootindex-start2;//左子树的长度
        //左子树
        TreeNode left=reConstructBinaryTree(pre,start1+1,start1+l,in,start2,start2+l-1);
        //右子树
        TreeNode right=reConstructBinaryTree(pre,start1+l+1,end1,in,rootindex+1,end2);
        //
        head.left=left;
        head.right=right;
        return head;
    }
    public int findIndexInArray(int[] array,int data,int start,int end)
    {
        for (int i = start; i <= end; i++)
        {
            if (array[i]==data)
                return i;
        }
        return -1;
    }
    public static void main(String[] args)
    {
        Solution solution = new Solution();

                solution.reConstructBinaryTree(new int[]{1,2,4,7,3,5,6,8},new int[]{4,7,2,1,5,3,8,6});

    }
}
